package 二叉树;

public class No236二叉树的最近公共祖先 {

    /**
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     *
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     *
     * 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
     *
     * 示例 1:
     *
     * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
     * 输出: 3
     * 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
     * 示例 2:
     *
     * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
     * 输出: 5
     * 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
     */

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //当前节点的两个孩子树分别包括了一个节点即可返回
        /**有两种情况:
         * 1.当前节点在目标节点中,只需在左右子树中找到一个即可返回
         * 2.当前节点非目标节点,左右节点需分别包含一个目标节点
         */
        return dg(root,p,q);
    }

    private TreeNode dg(TreeNode node,TreeNode p,TreeNode q){
        if(node==null)
            return null;
        if(node==p){
            boolean flag1 = findNode(node.left, q);
            if(flag1)
                return node;
            boolean flag2 = findNode(node.right, q);
            if(flag2)
                return node;
        }
        if(node==q){
            boolean flag1 = findNode(node.left, p);
            if(flag1)
                return node;
            boolean flag2 = findNode(node.right, p);
            if(flag2)
                return node;
        }
        //非目标节点
        //  ||  一个为true另外一个就不用计算了,就直接返回true,所以这种可以
        boolean flag1 = findNode(node.left, p)||findNode(node.left, q);
        boolean flag2 = findNode(node.right, q)||findNode(node.right, p);
        if(flag1&&flag2) {
            return node;
        }
        if(flag1){
            return dg(node.left,p,q);
        }else{
            return dg(node.right,p,q);
        }
    }

    private boolean findNode(TreeNode root,TreeNode node){
        if(root==null)
            return false;
        if(root==node)
            return true;
        //这里其实也可以用 ||
//        return findNode(root.left,node)||findNode(root.right,node);
        boolean flag1 = findNode(root.left, node);
        if(flag1)
            return true;
        boolean flag2 = findNode(root.right, node);
        if(flag2)
            return true;
        return false;
    }

    public TreeNode lowestCommonAncestorGood(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)
            return null;
        if(root==q||root==p)
            return root;
        TreeNode leftNode = lowestCommonAncestorGood(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestorGood(root.right, p, q);
        if(leftNode!=null&&rightNode!=null)//正好为当前节点
            return root;
        return leftNode==null?rightNode:leftNode;//一边节点
    }

    public static void main(String[] args) {
        No236二叉树的最近公共祖先 n=new No236二叉树的最近公共祖先();
        TreeNode n1=new TreeNode(1);
        TreeNode n2=new TreeNode(2);
        TreeNode n3=new TreeNode(3);
        n1.left=n2;
        n1.right=n3;
        TreeNode node = n.lowestCommonAncestorGood(n1, n3, n2);
        System.out.println(node.val);
    }

}